package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class _301_RemoveInvalidParentheses {
    public static void main(String[] args) throws InterruptedException {
        Solution solution = new _301_RemoveInvalidParentheses().new Solution();
        String s = ")(";
        List<String> strings = solution.removeInvalidParentheses(s);
        strings.forEach(System.out::println);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    public class Solution {

        int len;
        Set<String> set = new HashSet<>();
        StringBuilder path = new StringBuilder();
        char[] charArray;

        /**
         * @param idx         遍历的下标
         * @param leftCount   已经遍历的左括号的个数
         * @param rightCount  已经遍历的右括号的个数
         * @param leftRemove  最少应该删除的左括号的个数
         * @param rightRemove 最少应该删除的右括号的个数
         */
        private void dfs(int idx, int leftCount, int rightCount, int leftRemove, int rightRemove) {
            if (idx == len) {
                if (leftRemove == 0 && rightRemove == 0) {
                    set.add(new String(path));
                }
                return;
            }

            char c = charArray[idx];
            // 删除当前字符
            if (c == '(' && leftRemove > 0) {
                dfs(idx + 1, leftCount, rightCount, leftRemove - 1, rightRemove);
            } else if (c == ')' && rightRemove > 0) {
                dfs(idx + 1, leftCount, rightCount, leftRemove, rightRemove - 1);
            }

            // 保留当前字符
            path.append(c);
            if (c != '(' && c != ')') {
                dfs(idx + 1, leftCount, rightCount, leftRemove, rightRemove);
            } else if (c == '(') {
                dfs(idx + 1, leftCount + 1, rightCount, leftRemove, rightRemove);
            } else {
                if (leftCount > rightCount) {
                    dfs(idx + 1, leftCount, rightCount + 1, leftRemove, rightRemove);
                }
            }
            path.deleteCharAt(path.length() - 1);
        }

        public List<String> removeInvalidParentheses(String s) {
            this.len = s.length();
            int leftRemove = 0, rightRemove = 0;
            charArray = s.toCharArray();
            for (char c : charArray) {
                if (c == '(') {
                    leftRemove++;
                } else if (c == ')') {
                    if (leftRemove > 0) {
                        leftRemove--;
                    } else {
                        rightRemove++;
                    }
                }
            }
            dfs(0, 0, 0, leftRemove, rightRemove);
            return new ArrayList<>(set);
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}